import java.util.Stack;

public class Sort {
    //直接插入排序
    public static void insertSort(int[] arr){
        for (int i=1;i<arr.length;i++){
            int cur=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>cur){
                  arr[j+1]=arr[j];
                }
               else {
                    break;
                }
            }
            arr[j+1]=cur;//疑惑
        }
    }
    //希尔排序
    public static void shellSort(int[] arr){
        int gap=arr.length;
        while (gap>1){
            gap=gap/2;
            shell(arr,gap);
        }
    }
    public static void shell(int[] arr,int gap){
        for (int i=gap;i<arr.length;i++){
            int cur=arr[i];
            int j=i-gap;
            for (;j>=0;j=j-gap){
                if(arr[j]>cur){
                    arr[j+gap]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap]=cur;
        }
    }
    //选择排序
    public  static void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public static void selectSort(int[] arr){
        for (int i=0;i<arr.length;i++){
            int min=i;

            for (int j=i+1;j<arr.length;j++){
                if(arr[j]<min){
                    min=j;
                }
            }
          swap(arr,i,min);
        }
    }
   //双向选择排序
   public static void selectSortr(int[] arr){
        int l=0;
        int r=arr.length-1;
       while (l<r){
           int min=l;
           int max=r;
           for (int i=l+1;i<=r;i++){
               if(arr[i]<arr[min]){
                   min=i;
               }
               if(arr[i]>arr[max]){
                   max=i;
               }
           }
           swap(arr,l,min);
//           if(max==l){
//               max=min;
//           }
           swap(arr,r,max);
           l++;
           r--;
       }
   }
   //冒泡排序
    public static void bubbleSort(int[] array) {
        boolean flag=true;
        for (int i=0;i<array.length-1;i++){
            for (int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    swap(array,j+1,j);
                    flag=false;
                }
            }
            if (flag){
                return;
            }
        }
    }
    //快速排序
    public static void quikSort(int[] array) {
        quik(array,0,array.length-1);
    }

    private static void quik(int[] array, int start, int end) {
        if(end<=start){
            return;
        }
   /**
    * 优化1：当越来越有序的时候采用直接插入排序
    */
    if(end-start<=15){
        insertSort(array,start,end);
        return;
    }
        /**
         * 优化2：坐标尽量对半分
         * 1 2 3 4 5 6 7
         * 4 2 3 1 5 6 7
         */
    int index=middleNum(array,start,end);
    swap(array,start,index);


    //传统方法：
        //int pivot=partition(array,start,end);
    //挖坑法
        int pivot=partitionHole(array,start,end);
        quik(array,start,pivot-1);
        quik(array,pivot+1,end);

    }
    /*
    *返回三个坐标中，值为中间的坐标
     */
    private static int middleNum(int[] array, int start, int end) {
        int middle=(start+end)/2;
        if(array[start]<array[end]){
            if (array[middle]<array[start]){
                return start;
            }else if(array[middle]>array[end]){
                return end;
            }else {
                return middle;
            }
        }else{
            //array[start]>array[end]
            if(array[middle]>array[start]){
                return start;
            }else if(array[middle]<array[end]){
                return end;
            }else {return middle;}
        }
    }

    //重写插入排序
    private static void insertSort(int[] array, int start, int end) {
       for (int i=start+1;i<array.length;i++){
           int tmp=array[i];
           int j=i-1;
           for (;j>=0;j--){
            if(array[j]>tmp){
                array[j+1]=array[j];
            }
            else {
                break;
            }
           }
           array[j+1]=tmp;
       }
    }
    /*
    * 传统方法:
    * 在右边找到比tmp小的
    * 在左边找到比tmp大的
    * 交换
    * */
    private static int partition(int[] array, int start, int end) {
        int l=start;
        int r=end;
        int tmp=array[l];
        while (l<r){
            //需要加=符号，为了避免死循环
            while (l<r&&array[r]>=tmp){
                r--;
            }
            while (l<r&&array[l]<=tmp){
                l++;
            }
            swap(array,l,r);
        }
        swap(array,l,start);
        return l;
    }
    /*
    * 挖坑法：
    *
    * */
    private static int partitionHole(int[] array, int left, int right) {
        int tmp=array[left];
        while (left<right){
            while (left<right&&array[right]>tmp){
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left]<tmp){
                left--;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //快排非递归
    public static void quickSortNor(int[] array) {
        int start=0;
        int end=array.length-1;
        Stack<Integer> stack=new Stack<>();
        int pivot=partitionHole(array,start,end);
        if(start+1<pivot){
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot+1<end){
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()){
             end=stack.pop();
             start=stack.pop();
            pivot=partitionHole(array,start,end);
            if(start+1<pivot){
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot+1<end){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
    //技术排序
    public static void countSort(int[] array) {
        int max=array[0];
        int min=array[0];
        for (int i=0;i<array.length;i++){
            if (array[i]>max){
                max=array[i];
            }
            if(array[i]<min){
                min=array[i];
            }
        }
        int len=max-min+1;
        int[] count=new int[len];
        for (int j=0;j<array.length;j++){
            int a=array[j];
            count[a-min]++;
        }
        int index=0;
        for (int t=0;t<count.length;t++){
            while (count[t]>0){
                array[index]=t+min;
                count[t]--;
                index++;
            }
        }
    }
}
